package main

import "fmt"

func main() {
	fmt.Println(largestRectangleArea([]int{2, 1, 2}))
	fmt.Println(largestRectangleArea([]int{1}))
	fmt.Println(largestRectangleArea([]int{0}))
	//fmt.Println(largestRectangleArea([]int{2, 1, 5, 6, 2, 3}))
	//fmt.Println(largestRectangleArea([]int{4, 2, 0, 3, 2, 5}))
	//fmt.Println(largestRectangleArea([]int{3, 6, 5, 7, 4, 8, 1, 0}))
}
func largestRectangleArea(heights []int) int {
	length := len(heights)
	if length == 0 {
		return 0
	}
	left, right := make([]int, length+2), make([]int, length+2)
	stack := make([]int, length+2)
	tail := 0
	exHeights := make([]int, length+2)
	copy(exHeights[1:length+1], heights)
	for i := 1; i < length+2; i++ {
		if exHeights[i] > exHeights[stack[tail]] {
			left[i] = i - 1
			tail++
			stack[tail] = i
		} else if exHeights[i] == exHeights[stack[tail]] {
			left[i] = left[stack[tail]]
			tail++
			stack[tail] = i
		} else {
			for exHeights[i] < exHeights[stack[tail]] {
				right[stack[tail]] = i
				tail--
			}
			left[i] = stack[tail]
			tail++
			stack[tail] = i
		}
	}
	ans := 0
	for i, h := range exHeights {
		if area := h * (right[i] - left[i] - 1); area > ans {
			ans = area
		}
	}
	return ans
}

func largestRectangleArea2(heights []int) int {
	length := len(heights)
	if length == 0 {
		return 0
	}
	left, right := make([]int, length), make([]int, length)
	stack := make([]int, length)
	stack[0] = 0
	tail := 0
	for i := 1; i < length; i++ {
		if tail == -1 || heights[i] > heights[stack[tail]] {
			left[i] = i
			tail++
			stack[tail] = i
		} else if heights[i] == heights[stack[tail]] {
			left[i] = left[stack[tail]]
			tail++
			stack[tail] = i
		} else {
			for tail >= 0 && heights[i] < heights[stack[tail]] {
				right[stack[tail]] = i
				tail--
			}
			if tail >= 0 {
				left[i] = stack[tail] + 1
				tail++
				stack[tail] = i

			} else {
				stack[0] = i
				tail = 0
				left[i] = 0
			}
		}
	}
	for i := 0; i <= tail; i++ {
		right[stack[i]] = stack[tail] + 1
	}
	fmt.Println(heights, left, right, stack, tail)
	ans := 0
	for i, h := range heights {
		if area := h * (right[i] - left[i]); area > ans {
			ans = area
		}
	}
	return ans
}
